package com.fe.class08;

import java.util.Arrays;

/**
 * @Description 桶排序—计数排序（桶表示数组范围中的所有元素，有多少元素，则有多少桶）
 * 计数排序要求，样本是整数，且范围比较窄
 * @Author sosuke :-)
 * @Date 2022/1/12 21:24
 */
public class Code03_CountSort {

    /**
     * 计数排序
     * 这里的限制：arr数组中是非负 整数，且范围比较窄
     * @param arr
     */
    public static void countSort(int[] arr) {
        if (null == arr || arr.length < 2) return;
        int max = Integer.MIN_VALUE;
        for (int k : arr) {
            max = Math.max(max, k);
        }
        // 准备样本最大值加一个位置的桶，遍历arr，出现一个数，则该数对应的桶计数加一（arr中的元素对应桶的序号）
        // bucket[t] 表示arr中t有多少个
        int[] bucket = new int[max + 1];
        for (int m : arr) {
            bucket[m]++;
        }
        // 遍历所有桶，桶序号>0则表示这个arr元素（桶序号）出现多次
        int i = 0;
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0) {
                arr[i++] = j;
            }
        }
    }

    public static void main(String[] args) {
        int testTime = 500000; // 测试次数
        int maxSize = 100; // 数组数据个数
        int maxValue = 100; // 数组中最大值
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            countSort(arr1);
            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                System.out.println("Fuck");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                return;
            }
        }
        System.out.println("Nice");
        int[] arr = generateRandomArray(maxSize, maxValue);
        System.out.println(Arrays.toString(arr));
        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

}
